/*
 * @lc app=leetcode.cn id=46 lang=typescript
 *
 * [46] 全排列
 */

// @lc code=start
function permute(nums: number[]): number[][] {
  const ans: number[][] = [];
  const backtrack = (idx: number) => {
    if (idx === nums.length) {
      // 因为数组是引用类型，所以要做一次copy
      ans.push([...nums]);
      return;
    }
    for (let i = idx; i < nums.length; i++) {
      // 选择交换位置
      [nums[i], nums[idx]] = [nums[idx], nums[i]];
      // 递归下一个位置
      backtrack(idx + 1);
      // 回溯
      [nums[i], nums[idx]] = [nums[idx], nums[i]];
    }
  };

  backtrack(0);

  return ans;
}
// @lc code=end
